package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/longest-zigzag-path-in-a-binary-tree/'>二叉树中的最长交错路径(Longest ZigZag Path in a Binary Tree)</a>
 * <p>
 * 给你一棵以 root 为根的二叉树，二叉树中的交错路径定义如下：
 *     <ul>
 *         <li>选择二叉树中 任意 节点和一个方向（左或者右）。</li>
 *         <li>如果前进方向为右，那么移动到当前节点的的右子节点，否则移动到它的左子节点。</li>
 *         <li>改变前进方向：左变右或者右变左。</li>
 *         <li>重复第二步和第三步，直到你在树中无法继续移动。</li>
 *     </ul>
 *     交错路径的长度定义为：访问过的节点数目 - 1（单个节点的路径长度为 0 ）。
 * </p>
 * <p>请你返回给定树中最长 交错路径 的长度。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,1,1,1,null,null,1,1,null,1,null,null,null,1,null,1]
 *                          1
 *                           \
 *                            <a color='blue'>1</a>
 *                           / \
 *                          1   <a color='blue'>1</a>
 *                             / \
 *                            <a color='blue'>1</a>   1
 *                             \
 *                              <a color='blue'>1</a>
 *                               \
 *                                1
 *      输出：3
 *      解释：蓝色节点为树中最长交错路径（右 -> 左 -> 右）。
 *
 * 示例 2：
 *      输入：root = [1,1,1,null,1,null,null,1,1,null,1]
 *                          <a color='blue'>1</a>
 *                         / \
 *                        <a color='blue'>1</a>   1
 *                         \
 *                          <a color='blue'>1</a>
 *                         / \
 *                        <a color='blue'>1</a>   1
 *                         \
 *                          <a color='blue'>1</a>
 *      输出：4
 *      解释：蓝色节点为树中最长交错路径（左 -> 右 -> 左 -> 右）。
 *
 * 示例 3：
 *      输入：root = [1]
 *      输出：0
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>每棵树最多有 50000 个节点。</li>
 *     <li>每个节点的值在 [1, 100] 之间。</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/11/24 17:00
 */
public class _LC1372LongestZigZagPathInBinaryTree_M {
    static class Solution {
        int maxAns;

        public int longestZigZag(TreeNode root) {
            if (root == null) {
                return 0;
            }
            maxAns = 0;
            dfs(root, true, 0);
            dfs(root, false, 0);
            return maxAns;
        }

        private void dfs(TreeNode currNode, boolean isLeft, int length) {
            maxAns = Math.max(maxAns, length);
            // 当前节点向左
            if (isLeft) {
                if (currNode.right != null) {
                    dfs(currNode.right, false, length + 1);
                }
                if (currNode.left != null) {
                    dfs(currNode.left, true, 1);
                }
            }
            // 当前节点向右
            else {
                if (currNode.left != null) {
                    dfs(currNode.left, true, length + 1);
                }
                if (currNode.left != null) {
                    dfs(currNode.right, false, 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.right = new TreeNode(1);
        root1.right.left = new TreeNode(1);
        root1.right.right = new TreeNode(1);
        root1.right.right.left = new TreeNode(1);
        root1.right.right.right = new TreeNode(1);
        root1.right.right.left.right = new TreeNode(1);
        root1.right.right.left.right.right = new TreeNode(1);

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(1);
        root2.left.right = new TreeNode(1);
        root2.left.right.left = new TreeNode(1);
        root2.left.right.left.right = new TreeNode(1);
        root2.left.right.right = new TreeNode(1);
        root2.right = new TreeNode(1);

        TreeNode root3 = new TreeNode(1);

        Solution solution = new Solution();
        System.out.println(solution.longestZigZag(root1));
        System.out.println(solution.longestZigZag(root2));
        System.out.println(solution.longestZigZag(root3));
    }
}
